//
// Created by shenbin on 2022/5/13.
// https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
//

#ifndef ALGORITHM_TRAINNING_C05_LC297_H
#define ALGORITHM_TRAINNING_C05_LC297_H

#include <string>
#include <vector>
#include <sstream>
using namespace std;

class LeetCode297 {
public:
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;

        TreeNode() : val(0), left(nullptr), right(nullptr) {}

        TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}

        TreeNode(int _val, TreeNode *_left, TreeNode *_right) : val(_val), left(_left), right(_right) {}
    };
    string serialize(TreeNode* root){
        vector<string> seq;
        dfs(seq, root);
        string ans = "";
        for(int i=0; i<seq.size()-1; i++)
        {
            ans += seq[i] + ",";
        }
        if(seq.size() > 0)
        {
            ans += seq[seq.size()-1];
        }
        return ans;
    }

    TreeNode* deserialize(string data){
        stringstream ss(data);
        string s;
        while(getline(ss, s, ',')){
            res.push_back(s);
        }
        return restore();

    }
private:
    int curr;
    vector<string> res;
    void dfs(vector<string>& seq, TreeNode* root){
        if (root == nullptr){
            seq.push_back("null");
            return;
        }
        seq.push_back(to_string(root->val));
        dfs(seq, root->left);
        dfs(seq, root->right);
    }

    TreeNode* restore(){
        if(res[curr] == "null")
        {
            curr++;
            return nullptr;
        }
        TreeNode* root = new TreeNode(atoi(res[curr].c_str()));
        curr++;
        root->left = restore();
        root->right = restore();
        return root;
    }
};

#endif //ALGORITHM_TRAINNING_C05_LC297_H
